home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
PsL Monthly 1993 December
/
PSL Monthly Shareware CD-ROM (December 1993).iso
/
prgmming
/
win
/
general
/
atree.exe
/
lha
/
ATREE.DOC
< prev
next >
Wrap
Text File
|
1991-07-05
|
58KB
|
1,613 lines
An Implementation of Adaptive Logic Networks
~~ ~~~~~~~~~~~~~~ ~~ ~~~~~~~~ ~~~~~ ~~~~~~~~
copyright W.W. Armstrong and Andrew Dwelly
November 11, 1990
bug-fixes and initial port to DOS
Rolf Manderschied
April 15, 1991
revised for Microsoft Windows
Monroe M. Thomas
May 31, 1991
1 Introduction
~ ~~~~~~~~~~~~
The Windows dynamic link library atree.dll contains an implementation of
an unconventional kind of learning algorithm for adaptive logic
networks[Arms], which can be used in place of the backpropagation
algorithm for multilayer feedforward artificial neural networks [Hech],
[Rume].
The ability of a logic network to learn or adapt to produce an arbitrary
boolean function specified by some empirical "training" data is certainly
important for the success of the method, but there is another property of
logic networks which is also essential. It is the ability to generalize
their responses to new inputs, presented after training is completed. The
successful generalization properties of these logic networks are based on
the observation, backed up by a theory [Boch], that trees of two-input
logic gates of types AND, OR, LEFT, and RIGHT are very insensitive to
changes of their inputs.
Some experiments on handwritten numeral recognition and satellite image
classification have been successfully carried out. [Arms3, Arms4]. Recent
experiments have shown this algorithm to learn quickly on some problems
requiring learning of integer or continuous-valued functions where
backpropagation has reportedly led to long training times; and it
functions very well on boolean data [Arms5].
At the present time, only limited comparisons have been made with the
conventional approach to neurocomputing, so the claims necessarily have to
be muted. This situation should rapidly be overcome as users of this
software (or improved variants of it yet to come) begin experimentation.
However one property of these networks in comparison to others is an
absolute, and will become apparent to computer scientists just by
examining the basic architecture of the networks. Namely, when special
hardware is available, this technique, because it is based on
combinational logic circuits of limited depth (e. g. 10 to 20 propagation
delays), can potentially offer far greater execution speeds than other
techniques which depend on floating point multiplications, additions, and
computation of sigmoidal functions.
A description of the class of learning algorithms and their hardware
realizations can be found in [Arms, Arms2], but we will briefly introduce
the concepts here. An atree (Adaptive TREE) is a binary tree with nodes of
two types: (1) adaptive elements, and (2) leaves. Each element can
operate as an AND, OR, LEFT, or RIGHT gate, depending on its state. The
state is determined by two counters which change only during training.
The leaf nodes of the tree serve only to collect the inputs to the subtree
of elements. Each one takes its input bit from a boolean input vector or
from the vector consisting of the complemented bits of the boolean input
vector. The tree produces a single bit as its output.
-1-
Despite the apparent limitation to boolean data, simple table-lookups permit
representing non-boolean input values (integers or reals for example) as bit
vectors, and these representations are concatenated and complemented to form
the inputs at the leaves of the tree. For computing non-boolean outputs,
several trees are used in parallel to produce a vector of bits representing
the output value.
This software contains everything needed for a programmer with knowledge of
C and Windows 3.x to create, train, evaluate, and print out adaptive logic
networks. It has been written for clarity rather than speed in the hope that
it will aid the user in understanding the algorithms involved. The
intention was to try make this version faster than variants of the
backpropagation algorithm for learning, and to offer much faster evaluation
of learned functions than the standard approach given the same
general-purpose computing hardware. Users of the software are requested to
provide some feedback on this point to the authors.
This software also includes a language "lf" that allows a non-programmer
to conduct experiments using atrees, as well as a number of
demonstrations.
A version of this software which is both faster and contains a more
effective learning algorithm is planned for the near future.
Y
│
┌───────┴───────┐
│ Random Walk │
│ Decoder │
└───────┬───────┘
┌───────┴───────┐
│ Output Vector │
└┬─────────────┬┘
│ │
Trees - one per (O) (O)
output bit │ │
┌─────┴────┐ ┌─┴─┐
(O)─┘ └─(O)
│ │
┌─┴─┐ ┌─┴─┐
(O)┘ └(O) (O)┘ └(O)
┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐
│ │ │ │ │ │ │ │
b1 ~b1 b2 ~b1 ~b1 ~b2 b2 ~b2 Random Connections
┌──────┬──────┐
│ ~b1 │ ~b2 │ Complements
└──┬───┴──┬───┘
┌──────────────────┘ │
│ ┌──────────────────┘
┌──┴───┬──┴───┐
│ b1 │ b2 │ Input Vector
└──┬───┴──┬───┘
┌────┴──────┴───┐
│ Random Walk │
│ Encoder │
└───┬───────┬───┘
│ │
X1 X2
Figure 1: Using several trees to compute Y = ƒ(X1, X2)
-2-
2 Writing Applications With atree
~ ~~~~~~~ ~~~~~~~~~~~~ ~~~~ ~~~~~
Writing applications that perform a simple classification (yes or no) is
relatively easy (within the constraints of Windows programming). The
programmer creates a training set, then creates a tree using atree_create.
The tree is trained using atree_train and then it can be used to evaluate
new inputs using atree_eval. Examples of this can be seen in the files
mosquito.c, and mult.c, both of which hide most of Windows' dressings
for clarity.
Writing applications where the tree has to learn real number valued
functions is a little more complex, as the programmer has to come to grips
with the encoding problem.
Because a single tree produces only one bit, the programmer must train
several trees on the input data, each one responsible for one bit of the
output data. This is made slightly simpler by the choice of parameters
for atree_train() which takes an array of bit vectors as the training set,
and an array of bit vectors for the result set. The programmer provides
an integer which states which bit column of the result set the current tree
is being trained on. Typical code might look as follows:-
....
{
int i;
int j;
LPBIT_VEC train; /* LPBIT_VEC is a long (far) pointer to a bit_vec */
LPBIT_VEC result;
LPATREE *forest; /* LPATREE is a long (far) pointer to an atree */
/* Create the training set */
train = domain();
/* Create the result set */